/**
 * f[i] 表示总体积是 i 的情况下，最大价值是多少
 * result = max{f[0...m]}
 * for(i->n)
 *  for(j=v[i]->m)
 *      f[j] = max(f[j],f[j-v[i]]+w[i])
 * 
 *  for(int j = m ,i >= v[i];j--)
 *      for(int k = 0;k*v[i] <= k;k++)
 *          f[j] = max(f[j],f[j-k*v[i]]+k*w[i])
 * 数学归纳法：
 * 1. 假设考虑前 i-1 个物品后，所有的 f[i] 都是正确的
 * 2. 证明：考虑完第 i 个物品后，所有的 f[j] 也是正确的
 * 对于某个 j 而言，如果最优解 k 个 v[i]
 * f[j - k * v[i]] 
 * f[j - (k -1)* v[i] - v[i]] + w[i] 包含一个 v[i]
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int n,m;
int f[N]; // 堆里面的所有变量会被初始化为0

int main()
{
    cin >> n >> m;
    for(int i = 0;i < n;++i)
    {
        int v,w;
        cin >> v >> w;
        for(int j = v;j <= m;++j)
            f[j] = max(f[j],f[j-v]+w);
    }
    cout << f[m] << endl;
    return 0;
}